The present invention relates generally to secure communications and more particularly to schemes for certificate management.
In many settings, it is necessary to certify certain data, as well as to revoke already issued certificates. For instance, in a Public-Key Infrastructure, (PKI) it is necessary to certify users"" public keys.
In a digital signature scheme, each user U chooses a signing key SKU and a matching verification key, PKU. User U uses SKU to compute easily his digital signature of a message m, SIGU(m), while anyone knowing that PKU is U""s public key can verify that SIGU(m) is U""s signature of m. Finding SIGU(m) without knowing SKU is practically impossible. On the other hand, knowledge of PKU does not give any practical advantage in computing SKU. For this reason, it is in U""s interest to keep SKU secret (so that only he can digitally sign for U) and to make PKU as public as possible (so that everyone dealing with U can verify U""s digital signatures). At the same time, in a world with millions of users, it is essential in the smooth flow of business and communications to be certain that PKU really is the legitimate key of user U. To this end, users"" public keys are xe2x80x9ccertified.xe2x80x9d At the same time it is also necessary to revoke some of the already-issued certificates.
Typically, certificates for users"" public keys are produced and revoked by certifying authorities called CA""s.1 A CA can be considered to be a trusted agent having an already certified (or universally known) public key. To certify that PKU is U""s public key, a CA typically digitally signs PKU together with (e.g., concatenating it with) U""s name, a certificate serial number, the current date (i.e., the certification or issue date), and an expiration date.2 The CA""s signature of PKU is then inserted in a Directory and/or given to U himself.
1 A complete public-key infrastructure may involved other authorities (e.g., PCAs) who may also provide similiar services (e.g., they may certify the public keys to their CA""s). The present inventions can be easily applied to such other authorities. 
2 Before certifying U""s public key, it is neccesary to preform additional steps, such as properly identifying user U. The present invention, however, does not depend on these additional steps. 
Upon receiving the (alleged) digital signature of user U of a message M, SIGU(M), a recipient R needs to obtain a certificate for PKU. (indeed, SIGU(M) may be a correct digital signature of M with respect to some public key PKU, but R has no guarantee that PKU is indeed U""s public key). Recipient R may obtain this certificate from the Directory, or from his own memory (if he has previously cached it), or from U himself. Having done this, R verifies (1) the correctness of the CA""s certificate for PKU with respect to the CA""s public key, and (2) the correctness of SIGU(M) with respect to PKU. (If the CA""s public key is not universally known, or cached with R, then a certificate for this key too must be obtained.)
Certificate retrieval is thus possible, although not necessarily cheap. Unfortunately, however, this is not the only retrieval that R needs to do. Indeed, it is crucially important that R makes sure that the certificate for PKU has not been revoked. This check, of course, may not be needed after the certificate""s expiration date, but is needed during the certificate""s alleged lifetime. A user""s certificate can be revoked for a variety of reasons, including key compromise and the fact that the user is no longer associated with a particular CA.
To enable a recipient to establish whether a given certificate has been revoked, it is known that each CA periodically issues and gives the Directory a Certificate Revocation List (CRL for short), in general containing an indication of all the (not yet expired) certificates originally issued by it. A CRL typically consists of the issuer""s digital signature of (1) a header comprising the issuer""s name (as well as the type of his signature algorithm), the current date, the date of the last update, and the date of the next update, together with (2) a complete list of revoked certificates (whose date has not yet expired), each with its serial number and revocation date. Since it is expected that a CA revokes many of her certificates, a CRL is expected to be quite long.
After performing some checks on the CA""s CRL (e.g., checking the CA""s digital signature, checking that the CRL has arrived at the expected time, that a certificate declared revoked in the previous CRL of that CAxe2x80x94and not yet expiredxe2x80x94still is revoked in the current CRL, etc.), the Directory stores it under its CA name.
When a user queries the Directory about the revocation of a certificate issued by a given CA, the Directory responds by sending to the user the latest CRL of that CA. The user can then check the CRL signature, the CRL dates (so as to receive a reasonable assurance that he is dealing with the latest one), and whether or not the certificate of interest to him belongs to it.
While CRLs are quite effective in helping users establishing which certificates are no longer deemed valid, they are also extremely expensive, because they tend to be very long and need to be transmitted very often.
The National Institute of Standard and Technology has tasked the MITRE Corporation to study the organization and cost of a PKI for the Federal Government. This study estimates that CRLs constitute by far the largest entry in the Federal PKI""s cost list. According to MITRE""s estimates/assumptions, in the Federal PKI there are about three million users, each CA serves 30,000 users, 10% of the certificates are revoked,3 CRLs are sent out bi-weekly, and, finally, the recipient of a digital signature requests certificate information 20% of the time.4 The study envisages that each revoked certificate is specified in a CRL by means of about 9 bytes: 20 bits of serial number and 48 bits of revocation date. Thus, in the Federal PKI, each CRL is expected to comprise thousands of certificate serial numbers and their revocation dates; the header, however, has a fixed length, consisting of just 51 bytes.
3 5% because of key compromise and 5% because of change in affiliation with an organization connected to a given CA. 
4 The remaining 80% of the time he will be dealing with public keys in his cache. 
At 2 cents per kilobyte, the impact of CRL transmission on the estimated yearly costs of running the Federal PKI is stunning: if each federal employee verifies 100 digital signatures per day on average, then the total PKI yearly costs are $10,848 Millions, of which 10,237 Millions are due to CRL transmission. If each employee is assumed to verify just 5 digital signatures a day on average, then the total PKI yearly costs are $732 Millions, of which 563 Millions are due to CRL transmission.
The MITRE study thus suggests that any effort should be made to find alternative and cheaper CRL designs. This is indeed the goal of the present invention.
It is thus a primary object of the present invention to facilitate management of public key certificate revocation without providing users with lists of revoked certificates.
It is another primary object of the invention to provide certificate revocation information to users of a public key communications system wherein a user can receive an individual piece of information about any public key certificate instead of a large list of revoked certificates.
It is still another object of the invention to reduce dramatically the cost of managing public key certificates in part by reducing the size and number of transmissions by and among participants in the management scheme.
It is a still further object of the invention to provide novel certificate revocation schemes wherein a certifying authority can provide a positive and explicit statement about the validity status of each not-yet-expired certificate.
It is another object of the invention to allow certifying authorities to provide certificate validity information without requiring a trusted Directory.
It is a further object of the invention to provide a certificate management scheme wherein it is possible to prove that a given certificate was never issued or even existed.
The foregoing has outlined some of the more pertinent objects of the present invention. These objects should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial results can be attained by applying the disclosed invention in a different manner or modifying the invention as will be described. Accordingly, other objects and a fuller understanding of the invention may be had by referring to the following Detailed Description of the preferred embodiment.